#include "SeqList.h"

void SLInit(SL *psl)
{
    assert(psl);
    psl->a = NULL;
    psl->size = 0;
    psl->capacity = 0;
}

void SLDestroy(SL *psl)
{
    assert(psl);
    if (psl->a != NULL)
    {
        free(psl->a);
    }
    psl->size = psl->capacity = 0;
}

void SLPrint(SL *psl)
{
    assert(psl);
    for (int i = 0; i < psl->size; i++)
    {
        printf("%d ", psl->a[i]);
    }
    printf("\n");
}

void SLCheckCapacity(SL *psl)
{
    assert(psl);
    // 插入数据前要考虑空间是否已经满
    if (psl->size == psl->capacity)
    {
        // realloc如果对空扩容，就相当于malloc
        int newcapacity = psl->size == 0 ? 4 : psl->capacity * 2;
        // realloc氛围原地扩容和异地扩容，如果是异地扩容，realloc返回值就是新地址
        // 如果realloc异地扩容，会自动把旧空间free掉
        SLDataType *tmp = realloc(psl->a, sizeof(SLDataType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        // tmp存在的意义就是害怕赔了夫人又折兵
        psl->a = tmp;
        psl->capacity = newcapacity;
    }
}
void SLPushBack(SL *psl, SLDataType x)
{
    assert(psl);
    SLCheckCapacity(psl);

    psl->a[psl->size] = x;
    psl->size++;
}

// 顺序表头插时间复杂度O(N2)
void SLPushFront(SL *psl, SLDataType x)
{
    assert(psl);
    SLCheckCapacity(psl);
    int end = psl->size - 1;
    while (end >= 0)
    {
        psl->a[end + 1] = psl->a[end];
        end--;
    }
    psl->a[0] = x;
    psl->size++;
}

void SLPopFront(SL *psl)
{
    assert(psl);
    assert(psl->size > 0);
    int start = 1;
    while (start < psl->size)
    {
        psl->a[start - 1] = psl->a[start];
        ++start;
    }
    psl->size--;
}

void SLPopBack(SL *psl)
{
    assert(psl);
    // 如果此时size已经为0，那么直接size--会把size变负值
    // if (psl->size > 0)
    // {
    //     psl->size--;
    // }
    assert(psl->size > 0);
    psl->size--;
}

void SLInsert(SL *psl, int pos, SLDataType x)
{
    assert(psl);
    assert(pos >= 0 && pos <= psl->size);
    SLCheckCapacity(psl);

    int end = psl->size - 1;
    while (pos <= end)
    {
        psl->a[end + 1] = psl->a[end];
        --end;
    }
    psl->a[pos] = x;
    psl->size++;
}

void SLErase(SL *psl, int pos)
{
    assert(psl);
    assert(pos >= 0 && pos < psl->size);

    int start = pos + 1;
    while (start < psl->size)
    {
        psl->a[start - 1] = psl->a[start];
        start++;
    }
    psl->size--;
}

int SLFind(SL *psl, SLDataType x)
{
    assert(psl);
    for (int i = 0; i < psl->size; i++)
    {
        if (psl->a[i] == x)
        {
            return i;
        }
    }
    return -1;
}